//200. 岛屿数量

//给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
//岛屿总是被水包围，并且每座岛屿只能由水平方向和 / 或竖直方向上相邻的陆地连接形成。
//此外，你可以假设该网格的四条边均被水包围。

//class Solution {
//public:
//    int numIslands(vector<vector<char>>& grid) {
//        int n = grid.size(), m = grid[0].size(), ans{};
//        auto dfs = [&](this auto&& dfs, int x, int y) {//内函数dfs使用循环进行dfs可能使dfs未定义
//            if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == '0') {
//                return;
//            }
//            grid[x][y] = '0';
//            dfs(x - 1, y);
//            dfs(x + 1, y);
//            dfs(x, y - 1);
//            dfs(x, y + 1);
//            };
//
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j < m; j++) {
//                if (grid[i][j] == '1') {
//                    ans++;
//                    dfs(i, j);
//                }
//            }
//        }
//        return ans;
//    }
//};

//695. 岛屿的最大面积

//给你一个大小为 m x n 的二进制矩阵 grid 。
//岛屿 是由一些相邻的 1 (代表土地)构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
//岛屿的面积是岛上值为 1 的单元格的数目。
//计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

//class Solution {
//public:
//    int maxAreaOfIsland(vector<vector<int>>& grid) {
//        int m = grid.size(), n = grid[0].size();
//        int dirs[4][2] = { {0, -1}, {0, 1}, {-1, 0}, {1, 0} };
//        auto dfs = [&](this auto&& dfs, int i, int j) -> int {
//            int area = 1;
//            grid[i][j] = 0;
//            for (auto [dx, dy] : dirs) {
//                int x = i + dx, y = j + dy;
//                if (0 <= x && x < m && 0 <= y && y < n && grid[x][y]) {
//                    area += dfs(x, y);
//                }
//            }
//            return area;
//            };
//
//        int ans = 0;
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                if (grid[i][j]) {
//                    ans = max(ans, dfs(i, j));
//                }
//            }
//        }
//        return ans;
//    }
//};

//3619. 总价值可以被 K 整除的岛屿数目

//给你一个 m x n 的矩阵 grid 和一个正整数 k。一个 岛屿 是由 正 整数（表示陆地）组成的，并且陆地间 四周 连通（水平或垂直）。
//一个岛屿的总价值是该岛屿中所有单元格的值之和。
//返回总价值可以被 k 整除 的岛屿数量。

//class Solution {
//public:
//    int countIslands(vector<vector<int>>& grid, int k) {
//        int m = grid.size(), n = grid[0].size();
//        int dirs[4][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };
//        auto dfs = [&](this auto&& dfs, int i, int j) -> long long {
//            long long res = grid[i][j];
//            grid[i][j] = 0;
//            for (auto [dx, dy] : dirs) {
//                int x = i + dx, y = j + dy;
//                if (0 <= x && x < m && 0 <= y && y < n && grid[x][y]) {
//                    res += dfs(x, y);
//                }
//            }
//            return res;
//            };
//
//        int ans = 0;
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                if (grid[i][j] && dfs(i, j) % k == 0) {
//                    ans++;
//                }
//            }
//        }
//        return ans;
//    }
//};

//面试题 16.19. 水域大小

//你有一个用于表示一片土地的整数矩阵land，该矩阵中每个点的值代表对应地点的海拔高度。若值为0则表示水域。由垂直、水平或对角连接的水域为池塘。
//池塘的大小是指相连接的水域的个数。编写一个方法来计算矩阵中所有池塘的大小，返回值需要从小到大排序。

//class Solution {
//    int dfs(vector<vector<int>>& land, int x, int y) {
//        if (x < 0 || x >= land.size() || y < 0 || y >= land[x].size() || land[x][y]) {
//            return 0;
//        }
//        land[x][y] = 1;
//        int cnt0 = 1;
//        for (int i = x - 1; i <= x + 1; i++)
//            for (int j = y - 1; j <= y + 1; j++)
//                cnt0 += dfs(land, i, j);
//        return cnt0;
//    }
//
//public:
//    vector<int> pondSizes(vector<vector<int>>& land) {
//        int m = land.size(), n = land[0].size();
//        vector<int> ans;
//        for (int i = 0; i < m; i++)
//            for (int j = 0; j < n; j++)
//                if (land[i][j] == 0)
//                    ans.push_back(dfs(land, i, j));
//        sort(ans.begin(), ans.end());
//        return ans;
//    }
//};

//LCS 03. 主题空间

//「以扣会友」线下活动所在场地由若干主题空间与走廊组成，场地的地图记作由一维字符串型数组 grid，字符串中仅包含 "0"～"5" 这 6 个字符。
//地图上每一个字符代表面积为 1 的区域，其中 "0" 表示走廊，其他字符表示主题空间。相同且连续（连续指上、下、左、右四个方向连接）的字符组成同一个主题空间。
//假如整个 grid 区域的外侧均为走廊。请问，不与走廊直接相邻的主题空间的最大面积是多少？如果不存在这样的空间请返回 0。

//class Solution {
//public:
//    int largestArea(vector<string>& grid) {
//        int m = grid.size(), n = grid[0].size(), ans = 0;
//        int cnt;  // 面积
//        char cur; // 标记当前双重for循环遍历到的字符
//        int flag; // 标记是否是0的邻居，是0的邻居就不用它算最大值
//        auto dfs = [&](this auto&& dfs, int i, int j) -> void {
//            if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0') {
//                flag = 0;
//                return;
//            }
//            if (grid[i][j] != cur) {
//                return;
//            } 
//            cnt++;
//            grid[i][j] = '6';
//            dfs(i + 1, j);
//            dfs(i - 1, j);
//            dfs(i, j + 1);
//            dfs(i, j - 1);
//            };
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                if (grid[i][j] != '0' && grid[i][j] != '6') {
//                    cur = grid[i][j];
//                    flag = 1;
//                    cnt = 0;
//                    dfs(i, j);
//                    if (flag) {
//                        ans = max(cnt, ans);
//                    }
//                }
//            }
//        }
//        return ans;
//    }
//};

//463. 岛屿的周长

//给定一个 row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。
//网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。
//岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。

//class Solution {
//public:
//    int islandPerimeter(vector<vector<int>>& grid) {
//        int m = grid.size(), n = grid[0].size();
//        int ans = 0;
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                if (grid[i][j] == 0) {
//                    continue;
//                }
//                if (i == 0 || grid[i - 1][j] == 0) { // 上：出界或者是水
//                    ans++;
//                }
//                if (i == m - 1 || grid[i + 1][j] == 0) { // 下：出界或者是水
//                    ans++;
//                }
//                if (j == 0 || grid[i][j - 1] == 0) { // 左：出界或者是水
//                    ans++;
//                }
//                if (j == n - 1 || grid[i][j + 1] == 0) { // 右：出界或者是水
//                    ans++;
//                }
//            }
//        }
//        return ans;
//    }
//};

//2658. 网格图中鱼的最大数目

//给你一个下标从 0 开始大小为 m x n 的二维整数数组 grid ，其中下标在(r, c) 处的整数表示：
//如果 grid[r][c] = 0 ，那么它是一块 陆地 。
//如果 grid[r][c] > 0 ，那么它是一块 水域 ，且包含 grid[r][c] 条鱼。
//一位渔夫可以从任意 水域 格子(r, c) 出发，然后执行以下操作任意次：
//捕捞格子(r, c) 处所有的鱼，或者
//移动到相邻的 水域 格子。
//请你返回渔夫最优策略下， 最多 可以捕捞多少条鱼。如果没有水域格子，请你返回 0 。
//格子(r, c) 相邻 的格子为(r, c + 1) ，(r, c - 1) ，(r + 1, c) 和(r - 1, c) ，前提是相邻格子在网格图内。

//class Solution {
//public:
//    int findMaxFish(vector<vector<int>>& grid) {
//        int m = grid.size(), n = grid[0].size(), ans = 0;
//        int dirs[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
//        function<int(int, int)> dfs = [&](int x, int y) -> int {
//            if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == 0) {
//                return 0;
//            }
//            int sum = grid[x][y];
//            grid[x][y] = 0;
//            for (auto& d : dirs) {
//                sum += dfs(x + d[0], y + d[1]);
//            }
//            return sum;
//            };
//        for (int i = 0; i < m; ++i) {
//            for (int j = 0; j < n; ++j) {
//                ans = max(ans, dfs(i, j));
//            }
//        }
//        return ans;
//    }
//};

//1254. 统计封闭岛屿的数目

//二维矩阵 grid 由 0 （土地）和 1 （水）组成。岛是由最大的4个方向连通的 0 组成的群，封闭岛是一个 完全 由1包围（左、上、右、下）的岛。
//请返回 封闭岛屿 的数目。

//class Solution {
//    void dfs(vector<vector<int>>& grid, bool& closed, int x, int y) {
//        if (x == 0 || x == grid.size() - 1 || y == 0 || y == grid[x].size() - 1) {
//            if (grid[x][y] == 0) closed = false; // 到达边界
//            return;
//        }
//        if (grid[x][y]) return;
//        grid[x][y] = 1;
//        dfs(grid, closed, x - 1, y);
//        dfs(grid, closed, x + 1, y);
//        dfs(grid, closed, x, y - 1);
//        dfs(grid, closed, x, y + 1);
//    }
//
//public:
//    int closedIsland(vector<vector<int>>& grid) {
//        int m = grid.size(), n = grid[0].size(), ans = 0;
//        if (m < 3 || n < 3) return 0;
//        for (int i = 1; i < m - 1; i++) {
//            for (int j = 1; j < n - 1; j++) {
//                if (grid[i][j] == 0) {
//                    bool closed = true;
//                    dfs(grid, closed, i, j);
//                    ans += closed;
//                }
//            }
//        }
//        return ans;
//    }
//};

//130. 被围绕的区域

//给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' 组成，捕获 所有 被围绕的区域：
//连接：一个单元格与水平或垂直方向上相邻的单元格连接。
//区域：连接所有 'O' 的单元格来形成一个区域。
//围绕：如果您可以用 'X' 单元格 连接这个区域，并且区域中没有任何单元格位于 board 边缘，则该区域被 'X' 单元格围绕。
//通过 原地 将输入矩阵中的所有 'O' 替换为 'X' 来 捕获被围绕的区域。你不需要返回任何值。

//class Solution {
//public:
//    int m, n;
//
//    void dfs(vector<vector<char>>& board, int x, int y) {
//        if (x < 0 || x >= m || y < 0 || y >= n || board[x][y] != 'O') {
//            return;
//        }
//        board[x][y] = 'A';
//        dfs(board, x + 1, y);
//        dfs(board, x - 1, y);
//        dfs(board, x, y + 1);
//        dfs(board, x, y - 1);
//    }
//
//    void solve(vector<vector<char>>& board) {
//        m = board.size();
//        if (m == 0) {
//            return;
//        }
//        n = board[0].size();
//        for (int i = 0; i < m; i++) {
//            dfs(board, i, 0);
//            dfs(board, i, n - 1);
//        }
//        for (int i = 1; i < n - 1; i++) {
//            dfs(board, 0, i);
//            dfs(board, m - 1, i);
//        }
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                if (board[i][j] == 'A') {
//                    board[i][j] = 'O';
//                }
//                else if (board[i][j] == 'O') {
//                    board[i][j] = 'X';
//                }
//            }
//        }
//    }
//};

//1905. 统计子岛屿

//给你两个 m x n 的二进制矩阵 grid1 和 grid2 ，它们只包含 0 （表示水域）和 1 （表示陆地）。一个 岛屿 是由 四个方向 （水平或者竖直）上相邻的 1 组成的区域。任何矩阵以外的区域都视为水域。
//如果 grid2 的一个岛屿，被 grid1 的一个岛屿 完全 包含，也就是说 grid2 中该岛屿的每一个格子都被 grid1 中同一个岛屿完全包含，那么我们称 grid2 中的这个岛屿为 子岛屿 。
//请你返回 grid2 中 子岛屿 的 数目 。

//class Solution {
//public:
//    int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
//        int m = grid1.size(), n = grid1[0].size();
//        int dirs[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
//        bool flag = true;
//        auto dfs = [&](auto&& dfs, int i, int j) -> void {
//            grid2[i][j] = 0;
//            for (auto [dx, dy] : dirs) {
//                int x = dx + i, y = dy + j;
//                if (x >= 0 && x < m && y >= 0 && y < n && grid2[x][y]) {
//                    if (grid1[x][y] == 0) flag = false;
//                    dfs(dfs, x, y);
//                }
//            }
//            };
//
//        int ans = 0;
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                if (grid2[i][j] && grid1[i][j]) {
//                    flag = true;
//                    dfs(dfs, i, j);
//                    ans += flag;
//                }
//            }
//        }
//        return ans;
//    }
//};

//1391. 检查网格中是否存在有效路径

//给你一个 m x n 的网格 grid。网格里的每个单元都代表一条街道。grid[i][j] 的街道可以是：
//1 表示连接左单元格和右单元格的街道。
//2 表示连接上单元格和下单元格的街道。
//3 表示连接左单元格和下单元格的街道。
//4 表示连接右单元格和下单元格的街道。
//5 表示连接左单元格和上单元格的街道。
//6 表示连接右单元格和上单元格的街道。

//class Solution {
//    int m, n, dx[4] = { 1, 0, -1, 0 }, dy[4] = { 0, 1, 0, -1 }; // 0下、1右、2上、3左
//    int pipe[7][4] = { {-1, -1, -1, -1}, {-1, 1, -1, 3}, {0, -1, 2, -1},
//                      {-1, 0, 3, -1},   {-1, -1, 1, 0}, {3, 2, -1, -1},
//                      {1, -1, -1, 2} };
//    // 记录各个拼图块路径的方向，0、1、2、3代表方向，-1代表不可走。
//    bool vis[302][302];
//    bool dfs(int x, int y, int dir, vector<vector<int>>& grid) {
//        vis[x][y] = true;
//        if (x == m - 1 && y == n - 1) { // 到达终点
//            return true;
//        }
//        int xx = x + dx[dir];
//        int yy = y + dy[dir];
//        if (xx < 0 || yy < 0 || xx >= m || yy >= n) {
//            return false;
//        }
//        int nxt = grid[xx][yy];
//        if (pipe[nxt][dir] != -1 && !vis[xx][yy]) { // 如果当前方向可走，则方向改变，继续走
//            return dfs(xx, yy, pipe[nxt][dir], grid);
//        }
//        return false;
//    }
//
//public:
//    bool hasValidPath(vector<vector<int>>& grid) {
//        m = grid.size();
//        n = grid[0].size();
//        memset(vis, 0, sizeof(vis));
//        int sta = grid[0][0];
//        for (int i = 0; i < 4; ++i) { // 朝着四个方向都试一下
//            if (pipe[sta][i] != -1) { // 当前方向可以走
//                if (dfs(0, 0, pipe[sta][i], grid)) { // 沿着当前方向搜索
//                    return true;
//                }
//            }
//        }
//        return false;
//    }
//};

//417. 太平洋大西洋水流问题

//有一个 m × n 的矩形岛屿，与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界，而 “大西洋” 处于大陆的右边界和下边界。
//这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights ， heights[r][c] 表示坐标(r, c) 上单元格 高于海平面的高度 。
//岛上雨水较多，如果相邻单元格的高度 小于或等于 当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。
//返回网格坐标 result 的 2D 列表 ，其中 result[i] = [ri, ci] 表示雨水从单元格(ri, ci) 流动 既可流向太平洋也可流向大西洋 。

//class Solution {
//public:
//    vector<vector<int>> heights;
//    int dirs[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
//    void dfs(int row, int col, vector<vector<bool>>& ocean) {
//        int m = ocean.size();
//        int n = ocean[0].size();
//        if (ocean[row][col]) {
//            return;
//        }
//        ocean[row][col] = true;
//        for (int i = 0; i < 4; i++) {
//            int newRow = row + dirs[i][0], newCol = col + dirs[i][1];
//            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && heights[newRow][newCol] >= heights[row][col]) {
//                dfs(newRow, newCol, ocean);
//            }
//        }
//    }
//
//    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
//        this->heights = heights;
//        int m = heights.size();
//        int n = heights[0].size();
//        vector<vector<bool>> pacific(m, vector<bool>(n, false));
//        vector<vector<bool>> atlantic(m, vector<bool>(n, false));
//
//        for (int i = 0; i < m; i++) {
//            dfs(i, 0, pacific);
//        }
//        for (int j = 1; j < n; j++) {
//            dfs(0, j, pacific);
//        }
//        for (int i = 0; i < m; i++) {
//            dfs(i, n - 1, atlantic);
//        }
//        for (int j = 0; j < n - 1; j++) {
//            dfs(m - 1, j, atlantic);
//        }
//        vector<vector<int>> result;
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                if (pacific[i][j] && atlantic[i][j]) {
//                    vector<int> cell;
//                    cell.emplace_back(i);
//                    cell.emplace_back(j);
//                    result.emplace_back(cell);
//                }
//            }
//        }
//        return result;
//    }
//};

//529. 扫雷游戏

//让我们一起来玩扫雷游戏！
//给你一个大小为 m x n 二维字符矩阵 board ，表示扫雷游戏的盘面，其中：
//'M' 代表一个 未挖出的 地雷，
//'E' 代表一个 未挖出的 空方块，
//'B' 代表没有相邻（上，下，左，右，和所有4个对角线）地雷的 已挖出的 空白方块，
//数字（'1' 到 '8'）表示有多少地雷与这块 已挖出的 方块相邻，
//'X' 则表示一个 已挖出的 地雷。
//给你一个整数数组 click ，其中 click = [clickr, clickc] 表示在所有 未挖出的 方块（'M' 或者 'E'）中的下一个点击位置（clickr 是行下标，clickc 是列下标）。
//根据以下规则，返回相应位置被点击后对应的盘面：
//如果一个地雷（'M'）被挖出，游戏就结束了 - 把它改为 'X' 。
//如果一个 没有相邻地雷 的空方块（'E'）被挖出，修改它为（'B'），并且所有和其相邻的 未挖出 方块都应该被递归地揭露。
//如果一个 至少与一个地雷相邻 的空方块（'E'）被挖出，修改它为数字（'1' 到 '8' ），表示相邻地雷的数量。
//如果在此次点击中，若无更多方块可被揭露，则返回盘面。

//class Solution {
//public:
//    int dir_x[8] = { 0, 1, 0, -1, 1, 1, -1, -1 };
//    int dir_y[8] = { 1, 0, -1, 0, 1, -1, 1, -1 };
//
//    void dfs(vector<vector<char>>& board, int x, int y) {
//        int cnt = 0;
//        for (int i = 0; i < 8; ++i) {
//            int tx = x + dir_x[i];
//            int ty = y + dir_y[i];
//            if (tx < 0 || tx >= board.size() || ty < 0 || ty >= board[0].size()) {
//                continue;
//            }
//            cnt += board[tx][ty] == 'M';
//        }
//        if (cnt > 0) {
//            board[x][y] = cnt + '0';
//        }
//        else {
//            board[x][y] = 'B';
//            for (int i = 0; i < 8; ++i) {
//                int tx = x + dir_x[i];
//                int ty = y + dir_y[i];
//                // 这里不需要在存在 B 的时候继续扩展，因为 B 之前被点击的时候已经被扩展过了
//                if (tx < 0 || tx >= board.size() || ty < 0 || ty >= board[0].size() || board[tx][ty] != 'E') {
//                    continue;
//                }
//                dfs(board, tx, ty);
//            }
//        }
//    }
//
//    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
//        int x = click[0], y = click[1];
//        if (board[x][y] == 'M') {
//            board[x][y] = 'X';
//        }
//        else {
//            dfs(board, x, y);
//        }
//        return board;
//    }
//};

//1559. 二维网格图中探测环

//给你一个二维字符网格数组 grid ，大小为 m x n ，你需要检查 grid 中是否存在 相同值 形成的环。
//一个环是一条开始和结束于同一个格子的长度 大于等于 4 的路径。对于一个给定的格子，你可以移动到它上、下、左、右四个方向相邻的格子之一，可以移动的前提是这两个格子有 相同的值 。
//同时，你也不能回到上一次移动时所在的格子。比方说，环(1, 1) -> (1, 2) -> (1, 1) 是不合法的，因为从(1, 2) 移动到(1, 1) 回到了上一次移动时的格子。
//如果 grid 中有相同值形成的环，请你返回 true ，否则返回 false 。

//class Solution {
//public:
//    bool containsCycle(vector<vector<char>>& grid) {
//        int dirs[4][2] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
//        int R = grid.size(), C = grid[0].size();
//        vector<vector<int8_t>> vis(R, vector<int8_t>(C, false));
//
//        auto dfs = [&](this auto&& dfs, int r, int c, int pr, int pc) -> bool {
//            vis[r][c] = true;
//
//            for (auto [dr, dc] : dirs) {
//                int rr = r + dr;
//                int cc = c + dc;
//                if (rr < 0 || rr >= R || cc < 0 || cc >= C ||
//                    grid[rr][cc] != grid[r][c] || (rr == pr && cc == pc)) {
//                    continue;
//                }
//
//                if (vis[rr][cc] || dfs(rr, cc, r, c)) {
//                    return true;
//                }
//            }
//            return false;
//            };
//
//        for (int r = 0; r < R; r++) {
//            for (int c = 0; c < C; c++) {
//                if (!vis[r][c]) {
//                    if (dfs(r, c, r, c)) {
//                        return true;
//                    }
//                }
//            }
//        }
//
//        return false;
//    }
//};

//827. 最大人工岛

//给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。
//返回执行此操作后，grid 中最大的岛屿面积是多少？
//岛屿 由一组上、下、左、右四个方向相连的 1 形成。

//class Solution {
//public:
//    int largestIsland(vector<vector<int>>& grid) {
//        int n = grid.size();
//        int dirs[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
//        vector<int> area;
//        auto dfs = [&](this auto&& dfs, int i, int j) -> int {
//            grid[i][j] = area.size() + 2; // 记录 (i,j) 属于哪个岛
//            int size = 1;
//            for (auto& [dx, dy] : dirs) {
//                int x = i + dx, y = j + dy;
//                if (0 <= x && x < n && 0 <= y && y < n && grid[x][y] == 1) {
//                    size += dfs(x, y);
//                }
//            }
//            return size;
//            };
//
//        // DFS 每个岛，统计各个岛的面积，记录到 area 列表中
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j < n; j++) {
//                if (grid[i][j] == 1) {
//                    area.push_back(dfs(i, j));
//                }
//            }
//        }
//
//        // 特判没有岛的情况
//        if (area.empty()) {
//            return 1;
//        }
//
//        int ans = 0;
//        unordered_set<int> s;
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j < n; j++) {
//                if (grid[i][j]) continue;
//                s.clear();
//                int new_area = 1;
//                for (auto& [dx, dy] : dirs) {
//                    int x = i + dx, y = j + dy;
//                    if (0 <= x && x < n && 0 <= y && y < n && grid[x][y] && s.insert(grid[x][y]).second) {
//                        new_area += area[grid[x][y] - 2]; // 累加面积
//                    }
//                }
//                ans = max(ans, new_area);
//            }
//        }
//
//        // 如果最后 ans 仍然为 0，说明所有格子都是 1，返回 n^2
//        return ans ? ans : n * n;
//    }
//};

//LCP 63. 弹珠游戏

//欢迎各位来到「力扣嘉年华」，接下来将为各位介绍在活动中广受好评的弹珠游戏。
//N* M 大小的弹珠盘的初始状态信息记录于一维字符串型数组 plate 中，数组中的每个元素为仅由 "O"、"W"、"E"、"." 组成的字符串。其中：
//"O" 表示弹珠洞（弹珠到达后会落入洞中，并停止前进）；
//"W" 表示逆时针转向器（弹珠经过时方向将逆时针旋转 90 度）；
//"E" 表示顺时针转向器（弹珠经过时方向将顺时针旋转 90 度）；
//"." 表示空白区域（弹珠可通行）。
//游戏规则要求仅能在边缘位置的 空白区域 处（弹珠盘的四角除外）沿 与边缘垂直 的方向打入弹珠，并且打入后的每颗弹珠最多能 前进 num 步。
//请返回符合上述要求且可以使弹珠最终入洞的所有打入位置。你可以 按任意顺序 返回答案。
//注意：若弹珠已到达弹珠盘边缘并且仍沿着出界方向继续前进，则将直接出界。

//class Solution {
//public:
//    vector<vector<int>> ballGame(int num, vector<string>& plate) {
//        int m = plate.size(), n = plate[0].size();
//        int dirs[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
//        auto check = [&](int x, int y, int d) -> bool {
//            int left = num;
//            while (plate[x][y] != 'O') {
//                if (left == 0)
//                    return false;
//                if (plate[x][y] == 'W')
//                    d = (d + 3) % 4;
//                else if (plate[x][y] == 'E')
//                    d = (d + 1) % 4;
//                x += dirs[d][0];
//                y += dirs[d][1];
//                if (x < 0 || x >= m || y < 0 || y >= n)
//                    return false;
//                left--;
//            }
//            return true;
//            };
//
//        vector<vector<int>> ans;
//        for (int i = 1; i < m - 1; ++i) {
//            if (plate[i][0] == '.' && check(i, 0, 0)) // 左边
//                ans.push_back({ i, 0 });
//            if (plate[i][n - 1] == '.' && check(i, n - 1, 2)) // 右边
//                ans.push_back({ i, n - 1 });
//        }
//        for (int i = 1; i < n - 1; ++i) {
//            if (plate[0][i] == '.' && check(0, i, 1)) // 上边
//                ans.push_back({ 0, i });
//            if (plate[m - 1][i] == '.' && check(m - 1, i, 3)) // 下边
//                ans.push_back({ m - 1, i });
//        }
//        return ans;
//    }
//};